home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 4589 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: druid.borland.com!usenet
  2. From: pete@borland.com (Pete Becker)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 5 Feb 1996 23:35:21 GMT
  6. Organization: Borland International
  7. Message-ID: <4f647p$lc5@druid.borland.com>
  8. References: <4e61iu$p6e@villa.fc.net> <4e72il$dvl@ns.RezoNet.NET>
  9. NNTP-Posting-Host: pbecker.borland.com
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <4e72il$dvl@ns.RezoNet.NET>, ray@ultimate-tech.com says...
  15. >
  16. >In referenced article, Avinash Chopde says...
  17. >>I am trying to find out what could be the fastest way to compute
  18. >>the position of the highest bit in any given integer -- basically, the
  19. >>logarithm to the base 2 of any number.
  20. >
  21. >I can't think of any way faster than a variation of:
  22. >
  23. >/* Returns the Bitnumber of the highest set bit in n.
  24. >   Assumes an int is maximum 32-bits long.
  25. >   Returns -1 if n == 0
  26. >
  27. >   Log2Table is a table filled with the bit-number of the highest bit
  28. >   of the numbers 0 through 15
  29. >*/
  30. >
  31. >int FindHighestBitNumber(unsigned int n)
  32. >{ int i;
  33. >  static int Log2Table[16] =
  34. >    {-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
  35. >
  36. >  i = 0;
  37. >  if (n > 0xFFFF)
  38. >  {
  39. >    n = (n >> 16) & 0xFFFF;
  40. >    i = 16;
  41. >  }
  42. >  if (n > 0xFF)
  43. >  {
  44. >    n = n >> 8;
  45. >    i += 8;
  46. >  }
  47. >  if (n > 0xF)
  48. >  {
  49. >    n = n >> 4;
  50. >    i += 4;
  51. >  }
  52. >  return(Log2Table[n] + i);
  53. >}
  54. >
  55. >You could also use a union to extract the appropriate byte if speed is 
  56. >a concern and shifting is slow on your machine.
  57. >
  58. >If you want more speed, then give a 256 entry Log2Table and remove the 
  59. >last conditional.
  60.  
  61. Still faster: use a table with INT_MAX entries and remove all of the 
  62. conditionals. Why do the responses here assume that sacrificing speed for 
  63. space savings is appropriate? The question asks for the fastest, not something 
  64. that's reasonably fast but doesn't use much space.
  65.  
  66.